Fermat Pseudoprime
The motivation for the definition of a pseudoprime comes from Fermat's little theorem. Specifically, we consider the statement of the converse of Fermat's little theorem, which we have no justification in claiming is a true statement:
Given a prime \(p\) and number \(a\) where \(\mathrm{gcd}(a, p) = 1\), if \(a^{p - 1} \equiv 1 \pmod p\), then \(p\) is prime.
This statement is not true. Consider the following counterexample:
\(n = 15\) is a non prime number which satisfies:
when \(a = 4\).
Numbers which satisfy this property are called Fermat pseudoprimes, because with respect to Fermat's little theorem, they act like prime numbers, but are not.
If \(n\) is a composite number which satisfies:
for some \(a \in \mathbb{Z}\), then \(n\) is called a Fermat pseudoprime to the base \(a\).
Hence, in the language of this definition, \(15\) is a Fermat pseudoprime to the base \(4\).
Numbers which are pseudoprime to all coprime bases are called Carmichael numbers.